<html>
 <head>
  <link href="./leetcode-problem.css" rel="stylesheet" type="text/css">
 </head>
 <body>
  <div class="question_difficulty">
   难度：Hard
  </div>
  <div>
   <h1 class="question_title">
    911. Profitable Schemes
   </h1>
   <p>
    There are G people in a gang, and a list of various crimes they could commit.
   </p>
   <p>
    The
    <code>
     i
    </code>
    -th crime generates a
    <code>
     profit[i]
    </code>
    and requires
    <code>
     group[i]
    </code>
    gang members to participate.
   </p>
   <p>
    If a gang member participates in one crime, that member can't participate in another crime.
   </p>
   <p>
    Let's call a
    <em>
     profitable&nbsp;scheme
    </em>
    &nbsp;any subset of these crimes that generates at least
    <code>
     P
    </code>
    profit, and the total number of gang members participating in that subset of crimes is at most G.
   </p>
   <p>
    How many schemes can be chosen?&nbsp; Since the answer may be very&nbsp;large,
    <strong>
     return it modulo
    </strong>
    <code>
     10^9 + 7
    </code>
    .
   </p>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     Example 1:
    </strong>
   </p>
   <pre>
<strong>Input: </strong>G = <span id="example-input-1-1">5</span>, P = <span id="example-input-1-2">3</span>, group = <span id="example-input-1-3">[2,2]</span>, profit = <span id="example-input-1-4">[2,3]</span>
<strong>Output: </strong><span id="example-output-1">2</span>
<strong>Explanation: </strong>
To make a profit of at least 3, the gang could either commit crimes 0 and 1, or just crime 1.
In total, there are 2 schemes.
</pre>
   <div>
    <p>
     <strong>
      Example 2:
     </strong>
    </p>
    <pre>
<strong>Input: </strong>G = <span id="example-input-2-1">10</span>, P = <span id="example-input-2-2">5</span>, group = <span id="example-input-2-3">[2,3,5]</span>, profit = <span id="example-input-2-4">[6,7,8]</span>
<strong>Output: </strong><span id="example-output-2">7</span>
<strong>Explanation: </strong>
To make a profit of at least 5, the gang could commit any crimes, as long as they commit one.
There are 7 possible schemes: (0), (1), (2), (0,1), (0,2), (1,2), and (0,1,2).
</pre>
    <p>
     &nbsp;
    </p>
   </div>
   <p>
    <strong>
     Note:
    </strong>
   </p>
   <ol>
    <li>
     <code>
      1 &lt;= G &lt;= 100
     </code>
    </li>
    <li>
     <code>
      0 &lt;= P &lt;= 100
     </code>
    </li>
    <li>
     <code>
      1 &lt;= group[i] &lt;= 100
     </code>
    </li>
    <li>
     <code>
      0 &lt;= profit[i] &lt;= 100
     </code>
    </li>
    <li>
     <code>
      1 &lt;= group.length = profit.length &lt;= 100
     </code>
    </li>
   </ol>
   <div>
    <div>
     &nbsp;
    </div>
   </div>
  </div>
  <div>
   <h1 class="question_title">
    911. 盈利计划
   </h1>
   <p>
    帮派里有 G 名成员，他们可能犯下各种各样的罪行。
   </p>
   <p>
    第&nbsp;
    <code>
     i
    </code>
    &nbsp;种犯罪会产生&nbsp;
    <code>
     profit[i]
    </code>
    &nbsp;的利润，它要求&nbsp;
    <code>
     group[i]
    </code>
    &nbsp;名成员共同参与。
   </p>
   <p>
    让我们把这些犯罪的任何子集称为盈利计划，该计划至少产生&nbsp;
    <code>
     P
    </code>
    的利润。
   </p>
   <p>
    有多少种方案可以选择？因为答案很大，所以
    <strong>
     返回它模&nbsp;
    </strong>
    <code>
     10^9 + 7
    </code>
    <strong>
     &nbsp;的值
    </strong>
    。
   </p>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     示例&nbsp;1：
    </strong>
   </p>
   <pre><strong>输入：</strong>G = 5, P = 3, group = [2,2], profit = [2,3]
<strong>输出：</strong>2
<strong>解释： </strong>
至少产生 3 的利润，该帮派可以犯下罪 0 和罪 1 ，或仅犯下罪 1 。
总的来说，有两种方案。
</pre>
   <p>
    <strong>
     示例&nbsp;2:
    </strong>
   </p>
   <pre><strong>输入：</strong>G = 10, P = 5, group = [2,3,5], profit = [6,7,8]
<strong>输出：</strong>7
<strong>解释：</strong>
至少产生 5 的利润，只要他们犯其中一种罪就行，所以该帮派可以犯下任何罪行 。
有 7 种可能的计划：(0)，(1)，(2)，(0,1)，(0,2)，(1,2)，以及 (0,1,2) 。
</pre>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     提示：
    </strong>
   </p>
   <ol>
    <li>
     <code>
      1 &lt;= G &lt;= 100
     </code>
    </li>
    <li>
     <code>
      0 &lt;= P &lt;= 100
     </code>
    </li>
    <li>
     <code>
      1 &lt;= group[i] &lt;= 100
     </code>
    </li>
    <li>
     <code>
      0 &lt;= profit[i] &lt;= 100
     </code>
    </li>
    <li>
     <code>
      1 &lt;= group.length = profit.length &lt;= 100
     </code>
    </li>
   </ol>
   <p>
    &nbsp;
   </p>
  </div>
 </body>
</html>